package cn.wit.testalgorithms;

import java.util.Arrays;

import org.junit.Test;

/**
 * 整理排序算法，其中包含冒泡排序，选择排序，快速排序
 * 
 * @author 16604
 *
 */
public class DemoSortAlgorithm {
	public static void main(String[] args) {
		int[] data = { 1, 23, 4, 21, 4, 5 };

		// 冒泡排序
//		 System.out.println("冒泡排序："+Arrays.toString(bubbleSort(data)));

		// 选择排序
		// System.out.println("选择排序："+Arrays.toString(selectSort(data)));

		// //插入排序
		// System.out.println("插入排序"+insertSort(data));
		//
		// //快速排序
//		System.out.println("快速排序" + quickSort(data, 0, data.length - 1));
		//
		// //堆排序
		// System.out.println("堆排序"+heapSort(data));
	}

	// 冒泡排序
	@Test
	public static int[] bubbleSort(int[] data) {

		// 两层循环，第一层循环主要是次数，第二层循环才是核心

		for (int i = 1; i < data.length; i++) {
			boolean flag = true; // 优化冒泡排序
			for (int j = data.length - 1; j > i - 1; j--) {
				if (data[j] < data[j - 1]) {
					int temp;
					temp = data[j - 1];
					data[j - 1] = data[j];
					data[j] = temp;
					flag = false;
				}
			}
			if (flag == true) // 如果成立，说明数组已经排序好了，不需要重复呢
				break;
		}
		return data;

	}

	// 选择排序
	@Test
	public static int[] selectSort(int[] data) {
		/**
		 * 思想：每次都把要填的这个位置放上最小的， 排序完后，其结果自然是从小到大,开始前 默认自己当前位置元素的值最小
		 */
		int min;
		int pos;
		int temp;
		boolean flag;
		for (int i = 1; i < data.length; i++) {
			min = data[i - 1];
			pos = i - 1;
			flag = true;
			for (int j = i; j < data.length; j++) {
				if (min > data[j]) {
					min = data[j];
					pos = j;
					flag = false;
				}
			}
			if (flag == false) {
				temp = data[i - 1];
				data[i - 1] = data[pos];
				data[pos] = temp;
			}

		}
		return data;
	}

	// 插入排序
	public static int[] insertSort(int[] data) {
		return data;
	}

	// 快速排序
	@Test
	public static int[] quickSort(int[] data, int left, int right) {
		/**
		 * 快排是目前公认最佳排序法，时间复杂度为(n*logn) 先选左边跟右边，再拟定一个k=data[0]
		 * 开始一次是从右向左寻找首个小于k得元素位置，用找到得替换左边得 然后从左向右寻找首个大于k得元素位置，用找到得替换右边得
		 * 直到两边查询位置相等后，进行递归。
		 * (待调试)
		 */
		int k; // 用来存放数组元素
		int leftX; // 用来记录左边
		int rightY; // 用来记录右边

		// 对上述变量赋值
		leftX = left;
		rightY = right;

		k = data[leftX];

		do {
			// 先是从右边到左边遍历，找出首个小于k得位置
			while ((leftX < rightY) && (data[rightY] > k)) // 不满足就移动
				rightY--; // rightY左移

			if (leftX < rightY) {
				data[leftX] = data[rightY]; // 左边元素被右边元素替换
				leftX++; // 左边元素下标前进
			}

			// 再是从左边到右边遍历，找出首个大于k元素位置
			while ((leftX < rightY) && (data[leftX] < k))
				leftX++;// leftX右移

			if (leftX < rightY) {
				data[rightY] = data[leftX];
				rightY--;
			}
		} while (rightY != leftX);
		
		data[leftX] = k;//关键字定位
		
		//又一核心，递归
		quickSort(data, left, leftX-1);	//对左边部分排序
		quickSort(data, leftX+1, right);	//对左边部分排序

		return data;
	}

	// 堆排序
	@Test
	public static int[] heapSort(int[] data) {
		return data;
	}

}
